\documentclass{article}

\usepackage{amsmath, amsthm, amssymb, bm, color, framed, graphicx, hyperref, mathrsfs, ctex, listings, pgfplots}

\title{Homework3 Report}
\author{叶睿浩		3190104031}
\date{\today}

\begin{document}
	\maketitle
	这是homework3的Report
	
	\section{对题目的数学分析}
	题目要求我们返回树中所有值位于区间$[k_1,k_2]$中的元素的值，假设总共有$M$个这样的元素。
	
	我们有这样的引理：
	
	对于一个有序数组$\{a_n\}(n=1,\dotsb,N)$，其对应的任意一个AVL树$A$，打印树中元素$\{b_m\}(m=1,\dotsb,M)$，其中$b_1=a_{i},b_2=a_{i+1},\dotsb,b_M=a_{i+M-1}(i+M-1\leq N)$时，其时间成本为$O(M+\log N)$。
	
	对于这个引理的证明，我们可以将其分解为两步：首先是找到$b_1$、$b_M$即数列$\{b_m\}$的最小值和最大值，然后依照树的读取规则，将位于这个区间的所有元素打印出来。
	
	$\blacktriangleright$对于一棵AVLTree而言，其左右子树的高度之差的绝对值最多为1。因此当我们搜索AVLTree中的一个元素时，其开销最多为$O(\log N)$，其中$N$为树中所含的元素总数。因此我们很容易知道在树中寻找到两个元素的时间开销最多为$O(\log N)$（准确一点应该是$O(2\log N)$）。一旦找到最小值和最大值后，我们可以利用递归函数依次返回中间经历的元素的值，而这个过程只需要$O(M)$的时间成本，由此整个程序的时间成本为$O(M+\log N)$。$\blacktriangleleft$
	
	整个过程的代码大致如下：
	\begin{lstlisting}[language=C++]
void print(const DT &min, const DT &max, AvlNode* t) const
{
	if (t == nullptr)
	;
	else if(t->element >= min && t->element <= max)
	{
		print(min, max, t->left);
		cout << t->element << endl;
		print(min, max, t->right);
	}
		else if(t->element < min)
		print(min, max, t->right);
		
		else if(t->element > max)
		print(min, max, t->left);	
}
	\end{lstlisting}

	然后我们可以指出，往函数中的形参$\min,\max$传入$k_1,k_2$的值并不会影响这个函数的运行结果（前提是$k_1,k_2\in [\{a_n\}_{\min},\{a_n\}_{\max}]$）。因为总是可以找到一个元素$a_i$使其刚好满足$a_{i-1}<\min,a_i\geq\min$（对于$\max$也是如此）且这个操作的时间开销也是$O(\log N)$的。至此，我们证明了满足题目要求的程序其时间复杂度为$O(M+\log N)$。
	
	
	\section{程序验证}
	
	完成函数编写后，我们设计一个测试函数来验证这一分析。
	
	测试思路如下：
	
	1、固定$K=10$，改变$N$的大小（分别设置$N=10^2,10^3,\dotsb,10^6$），测试运行的时间耗费。
	
	2、固定$N=10^6$，改变$K$的大小（分别设置$K=10^2,10^3,\dotsb,10^6$），测试运行的时间耗费。
	
	测试结果制成图表如图\ref{fig1}所示。
	\begin{figure}[!h] %插入图片
		\centering %图片居中
		
		\begin{tikzpicture} %tikz图片
			
			\begin{loglogaxis}[
				xlabel=N/K, %横坐标名
				ylabel=Time(ms), %纵坐标名
				tick align=outside, %刻度在外显式
				legend style={at={(0.5,-0.2)},anchor=north} %图例在图下方显示
				]
				
				%第一条线，mark是折线标示形状
				\addplot[smooth,mark=*,blue] plot coordinates { 
					(100,3)
					(1000,2)
					(10000,3)
					(100000,7)
					(1000000,8)
				};
				
				%图例里名字
				\addlegendentry{改变N大小}
				
				%第二条线，mark是折线标示形状
				
				\addplot[smooth,mark=triangle,cyan] plot coordinates {
					(100,13)
					(1000,63)
					(10000,512)
					(100000,6239)
					(1000000,59080)
				};
				\addlegendentry{改变K大小}
				
			\end{loglogaxis}
		\end{tikzpicture}
		\caption{程序验证}
		\label{fig1}
	\end{figure}
	
	从图1中可以看到这个变化规律大致是符合我们前面的复杂度分析的结果的。
	
	

\end{document}